/*
 * @lc app=leetcode.cn id=124 lang=golang
 *
 * [124] 二叉树中的最大路径和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxPathSum(root *TreeNode) int {
	pathSum := -1 << 31
	var helper func(root *TreeNode) int
	helper = func(root *TreeNode) int {
		if root == nil {
			return 0
		}

		left := helper(root.Left)
		right := helper(root.Right)

		maxOneSidePath := max(root.Val, root.Val+max(left, right))

		pathSum = max(pathSum, max(maxOneSidePath, root.Val+left+right))
		return maxOneSidePath
	}

	helper(root)

	return pathSum
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// @lc code=end

